332. 重新安排行程

Similar Question

Solution Tips

方案一: 回溯 + N 叉树 + 快速退出

class Graph {
    vertices = [];
    adjList = new Map();

    addVertex(vertex) {
        this.vertices.push(vertex);
        this.adjList.set(vertex, []);
    }

    addEdge(v, u) {
        this.adjList.get(v).push(u)
    }

    toString() {
        let s = "";
        for (let i = 0; i < this.vertices.length; i++) {
            //{10}
            s += this.vertices[i] + " -> ";
            // 遍历该顶点的邻接表
            const neighbors = this.adjList.get(this.vertices[i]); //{11}
            for (let j = 0; j < neighbors.length; j++) {
                //{12}
                s += neighbors[j] + " ";
            }
            s += "\n"; //{13}
        }
        return s;
    }
}

var findItinerary = function (tickets) {
    // 先建图, 然后再深度优先搜索寻找最优路径
    // 当有多个可选路线时, 优先选择字典排序最小的那个即可
    const graph = new Graph();
    for (let i = 0; i < tickets.length; i++) {
        const [start, end] = tickets[i]
        if (!graph.adjList.has(start)) {
            graph.addVertex(start);
        }
        if (!graph.adjList.has(end)) {
            graph.addVertex(end);
        }
        graph.addEdge(start, end);
    }

    const color = getColor(graph);
    const res = ['JFK'];

    // 从 JFK 开始访问
    findTicket('JFK', color, []);
    // 不能标记顶点的颜色, 需要标记边的颜色
    function findTicket(v, color, chosen) {
        const neighbors = graph.adjList.get(v);

        if (neighbors.length === 0) {
            // 没有机票可以离开了, 看看是否符合条件
            // 快速退出
            return chosen.length === tickets.length && res.push(...chosen);
        }

        if (chosen.length === tickets.length) {
            res.push(...chosen);
            // 快速退出
            return true;
        }

        // 按照字典序排序
        neighbors.sort();
        for (let i = 0; i < neighbors.length; i++) {
            const u = neighbors[i];
            if (!color[v][i]) {
                chosen.push(u);
                color[v][i] = true;
                if (findTicket(u, color, chosen)) {
                    return true;
                }
                color[v][i] = false;
                chosen.pop();
            }
        }
    }

    function getColor(graph) {
        const color = {};
        for (const [vertex, neighbors] of graph.adjList) {
            color[vertex] = new Array(neighbors.length).fill(false);
        }
        return color;
    }
    return res;

};

可以优化的点:

1. 提前做字典序排序
2. 快速退出的 if else 简化, 优先判断长度
3. color 的逻辑简化, 从 color 数组简化为直接删除 neighbours, 但是需要保证迭代器不失效

var findItinerary = function(tickets) {
    let result = ['JFK']
    let map = {}

    for (const tickt of tickets) {
        const [from, to] = tickt
        if (!map[from]) {
            map[from] = []
        }
        map[from].push(to)
    }

    for (const city in map) {
        // 对到达城市列表排序
        map[city].sort()
    }
    function backtracing() {
        if (result.length === tickets.length + 1) {
            return true
        }
        if (!map[result[result.length - 1]] || !map[result[result.length - 1]].length) {
            return false
        }
        for(let i = 0 ; i <  map[result[result.length - 1]].length; i++) {
            let city = map[result[result.length - 1]][i]
            // 删除已走过航线，防止死循环
            map[result[result.length - 1]].splice(i, 1)
            result.push(city)
            if (backtracing()) {
                return true
            }
            result.pop()
            map[result[result.length - 1]].splice(i, 0, city)
        }
    }
    backtracing()
    return result
};

方案二: Hierholzer 算法

图的进阶算法

重新安排行程 - 重新安排行程 - 力扣（LeetCode）